package leetcode.f1t100;

import java.util.*;

/**
 * 给出数组, 目标, 返回任意个数字相加等于目标值的集合, 数字可重复使用
 * https://leetcode.com/problems/combination-sum/
 *
 * @Author lichongxiao
 * @Date 2022/10/12 14:54
 */
public class Q39_CombinationSum {
    public List<List<Integer>> combinationSum1(int[] candidates, int target) {
        List<List<Integer>> answers = new ArrayList<>();
        Set<String> answerKeys = new HashSet<>();
        process1(candidates, 0, target, new ArrayList(), answers,answerKeys);
        return answers;
    }

    private void process1(int[] candidates, int i, int target, ArrayList<Integer> listTemp, List<List<Integer>> answers,Set<String> answerKeys) {
        if (i == candidates.length || target < 0) {
            return;
        }
        if (target == candidates[i]) {

            listTemp.add(candidates[i]);
            StringBuilder sb = new StringBuilder();
            for(int num : listTemp){
                sb.append(num);
                sb.append("_");
            }
            String key = sb.toString();
            if(!answerKeys.contains(key)){
                answers.add(new ArrayList<>(listTemp));
                answerKeys.add(key);
            }
            listTemp.remove(listTemp.size() -1);
        }

        // 当前位置加入，不往后推
        listTemp.add(candidates[i]);
        process1(candidates, i, target - candidates[i], listTemp, answers,answerKeys);
        listTemp.remove(listTemp.size() -1);


        // 当前位置加入，往后推一位
        listTemp.add(candidates[i]);
        process1(candidates, i + 1, target - candidates[i], listTemp, answers,answerKeys);
        listTemp.remove(listTemp.size() -1);

        // 当前位置不加入，往后推一位
        process1(candidates, i + 1, target, listTemp, answers,answerKeys);
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Map<String, List<Integer>> answerMap = new HashMap<>();
        Arrays.sort(candidates);
        process(candidates, 0, target, new ArrayList(), answerMap);
        return new ArrayList<>(answerMap.values());
    }

    private void process(int[] candidates, int i, int target, ArrayList<Integer> listTemp, Map<String, List<Integer>> answerMap) {
        if (i == candidates.length || target < candidates[i]) {
            return;
        }
        if (target == candidates[i]) {
            listTemp.add(candidates[i]);
            StringBuilder sb = new StringBuilder();
            for(int num : listTemp){
                sb.append(num);
                sb.append("_");
            }
            String key = sb.toString();
            answerMap.put(key, new ArrayList<>(listTemp));
            listTemp.remove(listTemp.size() -1);
            return;
        }

        // 当前位置加入，不往后推
        listTemp.add(candidates[i]);
        process(candidates, i, target - candidates[i], listTemp, answerMap);
        listTemp.remove(listTemp.size() -1);


        // 当前位置加入，往后推一位
        listTemp.add(candidates[i]);
        process(candidates, i + 1, target - candidates[i], listTemp, answerMap);
        listTemp.remove(listTemp.size() -1);

        // 当前位置不加入，往后推一位
        process(candidates, i + 1, target, listTemp, answerMap);
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> answers = new ArrayList<>();
        Arrays.sort(candidates);
        process2(candidates, 0, target, new ArrayList<>(), answers);
        return answers;
    }

    private void process2(int[] candidates, int i, int target, ArrayList<Integer> tempList, List<List<Integer>> answers) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            answers.add(new ArrayList<>(tempList));
            return;
        }
        for (int j = i; j < candidates.length; j++) {

            tempList.add(candidates[j]);
            process2(candidates, j, target - candidates[j], tempList, answers);
            tempList.remove(tempList.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> answers = new Q39_CombinationSum().combinationSum(new int[]{2,5,8,4}, 10);
        for(List<Integer> answer : answers){
            for(Integer num : answer){
                System.out.print(num+" ");
            }
            System.out.println();
        }
    }
}
